/**
给你一个由 不同 整数组成的数组 nums ， 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)
请注意，顺序不同的序列被视作不同的组合。
 */
//回溯解法
function combinationSum4(nums, target) {
  const res = []
  const path = []
  nums.sort((a,b)=>a-b)
  const backTack = (sum) => {
    if (sum === target) {
      res.push(path.slice());
    }
    for(let i=0;i<nums.length;i++) {
      if(sum+nums[i]>target) break;
      path.push(nums[i])
      backTack(sum+nums[i], i);
      path.pop()
    }
  };
  backTack(0, 0)
  return res.length;
}
console.log(combinationSum4([1,2,3],4))
/**
元素取无限个--完全背包
虽然题目是组合数 但是描述里面的还是跟顺序有关 所以应该按照**排列数**来做
外层容量 内层物品数 dp下标是容量
dp[i] 容量为i的背包的组合数
 */
var combinationSum4 = function(nums, target) {
  const dp = Array(target+1).fill(0);
  dp[0]=1;
  for(let i=0; i<=target; i++){
    for(let j=0; j<nums.length;j++){
      if(i>=nums[j]){ //注意容量边界
        dp[i] += dp[i-nums[j]];
      }
    }
  }
  return dp[target];
};
const nums = [1,2,3], target = 4;
console.log('组合总和',combinationSum4(nums, target))

/**
 * review 1214✅
 */